#define _CRT_SECURE_NO_WARNINGS 1

//https://leetcode.cn/problems/target-sum/

class Solution {
    int ret = 0;
    int _target;
    int sum = 0;
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        _target = target;
        dfs(nums, 0);
        return ret;
    }

    void dfs(vector<int>& nums, int pos)
    {
        if (pos == nums.size())
        {
            if (sum == _target) ret++;
            return;
        }

        sum += nums[pos];
        dfs(nums, pos + 1);
        sum -= nums[pos];

        sum -= nums[pos];
        dfs(nums, pos + 1);
        sum += nums[pos];
    }
};